#include "hlss.h"
#include "Timer.h"
hlss::~hlss()
{
    delete R, C, R_max, C_max, row_ones, col_ones;
    for (int i = 0; i < node_count; i++)
    {
		free(tcm[i]); 
		free(tcm_orig[i]);
    }
    free(tcm); 
    free(tcm_orig);
}

hlss::hlss(Graph& g, int size, bool **matrix) : gra(g)
{
    node_count = size; cnt = 0; R_sz = C_sz = node_count;
    //coverred_row = coverred_col = 0;
    row_ones = new int[node_count];
    col_ones = new int[node_count];
    row_ones_orig = new int[node_count];
    col_ones_orig = new int[node_count];
    R_max = new char[node_count];
    C_max = new char[node_count];
    R = new char[node_count];
    C = new char[node_count];
    // (1)init TCM
    tcm = (int**)malloc( node_count * sizeof(int*));
    for (int i = 0; i < node_count; i++)
    {
		tcm[i] = (int*)malloc(node_count * sizeof (int));
		for (int j = 0; j < node_count; j++)
		{
			if(i==j)
				tcm[i][j] = 1;
			else
				tcm[i][j] = 0;
		}
    }
	if (matrix == NULL)
		calc_tcm();
	else
		copy_tcm(matrix);
    tcm_orig = (int**)malloc( node_count * sizeof(int*));
    for (int i = 0; i < node_count; i++)
    {
    	tcm_orig[i] = (int*)malloc(node_count * sizeof (int));
		for (int j = 0; j < node_count; j++)
		    tcm_orig[i][j] = tcm[i][j];
    }
    //(2) init row_ones, col_ones
    int one;
    for (int i = 0 ; i < node_count; i++)
    {
		one = 0;
		for (int j = 0; j < node_count; j++)
		{
			if ( tcm[i][j] == 1 ) one ++;
		}
		row_ones[i] = one;
		row_ones_orig[i] = one;
		R[i] = 1;
		R_max[i] = 1;
    }
    for (int i = 0 ; i < node_count; i++)
    {
		one = 0;
		for (int j = 0; j < node_count; j++)
		{
			if ( tcm[j][i] == 1 )
				one ++;
		}
		col_ones[i] = one;
		col_ones_orig[i] = one;
		C[i] = 1;
		C_max[i] = 1;
    }
    //(3) init Lout, Lin labels
    set<int> v;
    for (int i = 0; i < node_count; i++)
    {
		Lout.insert(make_pair(i,v));
		Lin.insert(make_pair(i,v));
    }
}

void hlss::calc_tcm()
{
    std::vector<Vertex> to_tc_vec(num_vertices(gra));
    VertexIndexMap index_map = get(&VertexProp::id, gra);
    iterator_property_map < Vertex *, VertexIndexMap, Vertex, Vertex&> g_to_tc_map(&to_tc_vec[0], index_map);
    transitive_closure(gra, tc, g_to_tc_map, index_map);
    graph_traits<Graph>::vertex_iterator vi, vi_end, v2, v2e;
    for (tie(vi, vi_end) = vertices(gra), tie(v2, v2e) = vertices(tc); vi != vi_end; ++vi, ++v2)
		tc[*v2].id = gra[*vi].id;   //copy ids
    boost::graph_traits<Graph>::in_edge_iterator ei, eiend;
    boost::graph_traits<Graph>::edge_iterator eit, e_start, e_end;
    std::pair<graph_traits<Graph>::edge_iterator, graph_traits<Graph>::edge_iterator> e_range;
    e_range = edges(tc);
    for (eit = e_range.first; eit != e_range.second; eit++)
    {
		tcm[gra[source(*eit,tc)].id][gra[target(*eit,tc)].id] = 1;
    }
}

void hlss::copy_tcm(bool **matrix)
{
	for (int i = 0; i < node_count; i++)
	{
		for (int j= 0 ; j < node_count; j++)
		{
			if (matrix[i][j] == false)
				tcm[i][j] = 1;
		}
	}
}

void hlss::update_label()
{
    for (int i = 0; i < node_count; i++)
    {
		if(R_max[i] == 1) Lout.find(i)->second.insert(cnt);
		if(C_max[i] == 1) Lin.find(i)->second.insert(cnt);
    }
}

void hlss::remove_zero()
{
	int row1,col1;
	for (int i = 0; i < node_count; i++)
    {
		if( R_max[i] == 0 ) continue;
		for ( int j = 0; j < node_count; j++)
		{
			if( C_max[j] == 0 ) continue;
			if( tcm[i][j] == 0 )
			{
				row1 =  col1 = 0;
				//count row ones
				for (int x = 0; x < node_count; x ++)
					if (C_max[x] == 1 and tcm[i][x] == 1)
						row1 ++;
				//count col ones
				for (int x = 0; x < node_count; x ++)
					if (R_max[x] == 1 and tcm[x][j] == 1)
						col1 ++;
				if (row1 < col1)
					R_max[i] = 0;
				else
					C_max[j] = 0;
			}
		}
    }
}

void hlss::collect_zero_exception()
{
    for (int i = 0; i < node_count; i++)
    {
		if( R_max[i] == 0 ) continue;
		for ( int j = 0; j < node_count; j++)
		{
			if( C_max[j] == 0 ) continue;
			if( tcm[i][j] == 0 )
			{
				zero_exception_set.insert(make_pair(i,j));
			}
		}
    }
}
void hlss::collect_one_exception()
{
    for (int i = 0; i < node_count; i++)
    {
		for ( int j = 0; j < node_count; j++)
		{
			if( tcm[i][j] == 1 and i != j)
			{
				one_exception_set.insert(make_pair(i,j));
			}
		}
    }
}
int hlss::create_label()
{
    while(true)
    {
		cnt ++; // loop count, also serve as the unique symbol "s".
		cout << endl << "Loop: " << cnt << endl;
		//print_tcm();
		findDSM();
		if ( (R_max_sz <=1 && C_max_sz <= 1) || den_max == 0)
			break;
		remove_zero();
		update_label();
		//collect_zero_exception();
		//print_tcm();
		remove_DSM();
		//scanf("%d", &temp);
    }
	collect_one_exception();
    print_label();
	int size = label_size();
	set_2_vector();
	return size;
}

void hlss::update_R_C_max()
{
    
	/*for (int i = 0; i < node_count; i++)
    {
		R_max[i] = R[i];
		C_max[i] = C[i];
	 }
	*/
	memcpy(R_max, R, node_count);
	memcpy(C_max, C, node_count);

	/*
	set<int>::iterator it;
	for (it = delete_row_set.begin(); it != delete_row_set.end(); it++)
	{
		R_max[*it] = 0;
	}
	for (it = delete_col_set.begin(); it != delete_col_set.end(); it++)
	{
		C_max[*it] = 0;
	}*/
    R_max_sz = R_sz;
	C_max_sz = C_sz;
}
//FindDSM_2APPROX, in Alg 5.1
void hlss::findDSM()
{
    den = -1; den_max = -1;
    int r,c, r_ones, c_ones, update_cnt;
    while (R_sz > 0 && C_sz > 0 )
    {
    	den = calc_den();
		//cout << "den:" << den << "den max:" << den_max;
		if (den > den_max)
		{
			update_R_C_max();
			den_max = den;
		}
		r = find_min_row();
		c = find_min_col();
		r_ones = r != -1 ? row_ones[r]:-1;
		c_ones = c != -1 ? col_ones[c]:-1;
		if ( ( r_ones < c_ones) || (r_ones ==  c_ones && R_sz > C_sz) )
		{
			/*delete row, update col_ones*/
			update_cnt = 0;
			for (int i = 0; i < node_count && update_cnt < r_ones; i++)
			{
				if (C[i] == 1 && tcm[r][i] == 1)
				{
					col_ones[i] --;
					update_cnt++;
				}
			}
			R[r] = 0; // 0 means the row is deleted from current loop
			R_sz --;
			//delete_row_set.insert(r);
			//cout << "Delete row " << r << " row_ones: " << r_ones << endl;
		}
		else
		{
			/*delete col, update row_ones*/
			update_cnt = 0;
			for (int i = 0; i < node_count && update_cnt < c_ones; i++)
			{
				if (R[i] == 1 && tcm[i][c] == 1)
				{
					row_ones[i] --;
					update_cnt ++;
				}
			}
			C[c] = 0;
			C_sz --;
			//delete_col_set.insert(c);
			//cout << "Delete col " << r << " col_ones: " << c_ones << endl;
		}
    }
    cout << endl <<  "den max = " << den_max << endl;
}

float hlss::calc_den()
{
    int n1 = N1();
    int n0 = R_sz * C_sz - n1;
    //int size_s = 1, size_e = 1;
    float den = (float) n1 / ( R_sz + C_sz+ n0 );
    //cout << "R_size:" << R_sz << " C_size:" << C_sz << " N_1:" << n1 << " N_0:" << n0 << " den:" << den << endl;
    return den;
}

//get the numnber of x in current loop; (x = 1 or 0)
int hlss::N1()
{
    int n1 = 0;
    for (int i = 0; i < node_count; i++)
    {
		if (R[i] == 1)
			n1 += row_ones[i];
    }
    return n1;
}

//find the row which has the min number of 1
int hlss::find_min_row()
{
    int min_r = -1;
    int min_n1 = INT_MAX;
    for (int i = 0; i < node_count; i++)
    {
		if (R[i] == 1) //still valid in current loop, not covered, not deleted
		{
			if (row_ones[i] < min_n1)
			{
				min_n1 = row_ones[i];
				min_r = i;
			}
		}
    }
    //assert(min_r != -1);
    return min_r;
}

int hlss::find_min_col()
{
    int min_c = -1;
    int min_n1 = INT_MAX;
    for (int i = 0; i < node_count; i++)
    {
		if (C[i] == 1) //still valid in current loop, not covered, not deleted
		{
			if (col_ones[i] < min_n1)
			{
				min_n1 = col_ones[i];
				min_c = i;
			}
		}
    }
    //assert(min_c != -1);
    return min_c;
}

/*
  remove the covered DSM from the TCM, 
*/
void hlss::remove_DSM()
{
	for (int i = 0; i < node_count; i++)
	{
		if (R_max[i] == 0 ) continue;
		for (int j = 0; j < node_count; j++)
		{
			if (C_max[j] == 1)
			{
				if (tcm[i][j] == 1)
				{
					row_ones_orig[i] --;
					col_ones_orig[j] --;
				}
				tcm[i][j] = -1;
			}
		}
	}
	
    /*for (int i = 0; i < node_count; i++)
    {
		//R_max[i] = C_max[i] = R[i] = C[i] = 1;
		row_ones[i] = row_ones_orig[i];
		col_ones[i] = col_ones_orig[i];
    }
	*/
	memset(R_max, 1, node_count);
	memset(C_max, 1, node_count);
	memset(R, 1, node_count);
	memset(C, 1, node_count);
	memcpy(row_ones, row_ones_orig, sizeof(int)*node_count);
	memcpy(col_ones, col_ones_orig, sizeof(int)*node_count);
	R_sz = C_sz = node_count;
}

void hlss::print_tcm()
{
    for (int i = 0; i < node_count; i++)
    {
		cout << endl;
		for (int j = 0; j < node_count; j++)
		{
			if (R_max[i] == 1 && C_max[j] == 1)
			{
				if (tcm[i][j] == 1)
					cout << "+ ";
				else if (tcm[i][j] == 0)
					cout << "- ";
			}
			else
			{
				if (tcm[i][j] == -1)
					cout << "* ";
				else
					cout << tcm[i][j] << " ";
			}
				
		}
    }
    cout << endl << "R_max:" << endl;
    for (int i = 0; i < node_count; i++)
    {
    	cout << R_max[i] << " ";
    }
    cout << endl << "C_max:" << endl;
    for (int i = 0; i < node_count; i++)
    {
    	cout << C_max[i] << " ";
    }
}

void hlss::print_label()
{
    map<int, set<int> >::iterator m_it;
    set<int>::iterator s_it;
    for (int i = 0; i < node_count; i++)
    {
		cout << i << ":" << endl << "Lout:(";
		m_it = Lout.find(i);
		for (s_it = m_it->second.begin(); s_it != m_it->second.end(); s_it++)
		{
			cout << *s_it << ", ";
		}
		cout << ")" << endl << "Lin:(";
		m_it = Lin.find(i);
		for (s_it = m_it->second.begin(); s_it != m_it->second.end(); s_it++)
		{
			cout << *s_it << ", ";
		}
		cout << ")" << endl;
    }
    cout << endl << "0 exception: " << endl;
    set<pair<int, int> >::iterator it;
    for (it = zero_exception_set.begin(); it != zero_exception_set.end(); it++)
    {
		cout << "(" << it->first << ", " << it->second << ")"  << "\t" ;
    }
    cout << endl << "1 exception: " << endl;
    for (it = one_exception_set.begin(); it != one_exception_set.end(); it++)
    {
		cout << "(" << it->first << ", " << it->second << ")"  << "\t" ;
    }
}

int hlss::label_size()
{
    int sz = 0;
    for (int i = 0; i < node_count; i++)
    {
		sz += Lout.find(i)->second.size();
		sz += Lin.find(i)->second.size();
    }
    return (sz + one_exception_set.size() + zero_exception_set.size());
}

bool hlss::query(int u, int v)
{
	vector<int>::iterator s_it1, s_it2;
	for (s_it1 = Lout_vec[u].begin(); s_it1 != Lout_vec[u].end(); s_it1++)
	{
		for (s_it2 = Lin_vec[v].begin(); s_it2 != Lin_vec[v].end(); s_it2++)
		{
			if (*s_it1 == *s_it2)
				return true;
		}
	}
	set<pair<int, int> >::iterator it;
	for (it = one_exception_set.begin(); it != one_exception_set.end(); it++)
	{
		if (it->first == u  && it->second == v)
			return true;
	}
	for (it = zero_exception_set.begin(); it != zero_exception_set.end(); it++)
	{
		if (it->first == u  && it->second == v)
			return false;
	}
	return false;
}

int hlss::batch_query(int size)
{
	//cout << "Generating " << query_size << " random queries...." << endl;
    srand48(time(NULL));
    int s, t;
    int left = 0;
    vector<int> src, trg;                                                  
    vector<int>::iterator sit, tit;
    int gsize = node_count;
    while (left < size)
    {
        s = lrand48() % gsize;
        t = lrand48() % gsize;
        if (s == t) continue;
        src.push_back(s);
        trg.push_back(t);
        ++left;
    }
    cout << "Processing queries..." << endl;
	int err = 0;
	Timer timer;
	timer.start();
    for (sit = src.begin(), tit = trg.begin(); sit != src.end(); sit++, tit++)
    {
		query(*sit, *tit);
        //if (query(*sit, *tit) != tcm_orig[*sit][*tit])  err ++;
    }
	cout << endl <<  "Query processing time:" << timer.stop() << "    ERR: " << err <<  endl;
}


void hlss::set_2_vector()
{
    Lin_vec = vector<vector<int> >(node_count, vector<int>());
    Lout_vec = vector<vector<int> >(node_count, vector<int>());
    map<int, set<int> >::iterator it;
    for (int i = 0; i < node_count; i++)
    {
        it = Lin.find(i);
        if (it != Lin.end())
        {
            Lin_vec[i].insert(Lin_vec[i].begin(), it->second.begin(), it->second.end());
        }
        it = Lout.find(i);
        if (it != Lout.end())
        {
            Lout_vec[i].insert(Lout_vec[i].begin(), it->second.begin(), it->second.end());
        }
    }	                                                                                                     
}

